package LeetCodeHot100;

/**
 * 最长回文子串
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 *  思路：使用动态规划解决问题
    分为三种情况 ，如果  j - i == 0， 肯定是回文的
                 如果  j - i == 1， 那么也是回文的, char（i） == char(j)
                 如果  dp[i+1][j-1] = true. 且 char(i) == char(j)， 那么dp[i][j] = true
    因为看公式是从外部推导到里边，所以
 */
public class LeetCode05 {
    public String longestPalindrome(String s) {

        if(s==null || s.length() == 0){
            return s;
        }
        char[] chars = s.toCharArray();
        String  res = "";
        boolean[][] dp = new boolean[s.length()][s.length()];
        for (int i = s.length()-1; i >=0 ; i--) {
            for (int j = i; j <s.length() ; j++) {
                if(j-i == 0){
                    dp[i][j] = true;
                } else if(j - i == 1 && s.charAt(i) == s.charAt(j)){
                    dp[i][j] = true;
                }else if(s.charAt(i) == s.charAt(j) && dp[i+1][j-1]){
                    dp[i][j] = true;
                }

                if(dp[i][j] && (j-i+1) > res.length()){
                    res = s.substring(i,j+1);
                }
            }
        }
        return res;
    }
}
